1. Field of the Invention
The present invention relates to an efficient and reliable convolutional encoder and sequential decoder system which uses the properties of block codes to maximize decoding efficiency and thereby greatly increase the speed and/or coding gain over the prior art.
2Description of Related Art
Convolutional encoding and sequential decoding have received considerable attention within the communications field. The properties of the various codes and popular decoding algorithms are discussed in detail in Error Control Coding: Fundamentals and Applications, Lin and Costello, Prentice-Hall, 1983 (pp. 350-384).
A conventional convolutional encoder comprises K shift registers coupled to N-K parity adders. Each adder acts on a distinct subset of the bits in the shift registers. Typically, the code is systematic. The N-K outputs of the adders are loaded into a parallel-to-serial register along with K successive data bits. This N-bit word is then transmitted in serial form. These N symbols form one "branch" of a "tree code" which is generated. For transmission purposes, the convolutionally encoded data is organized into packets. This packet of encoded data then becomes the initial state for the encoding of the next block of data.
Systematic convolutional encoding inserts parity bits into the information bit stream. The code words in the conventional convolutional code can be arranged in the form of a tree structure, and the encoder selects a path through the tree corresponding to the data to be encoded. Sequential decoding can accordingly be regarded as the process of determining the path in the tree which was followed by the encoder. As the decoder reconstructs the encoder's path through the tree based upon the received sequence, it compares the probability of the path that it is currently exploring against a threshold. The probability of a path is stored in the decoder as the "path metric". When the comparison is favorable, the decoder continues forward on the decoding tree. An unfavorable comparison indicates that the decoder is on the wrong path. In this event the decoder changes direction and searches a different portion of the tree.
A conventional sequential decoder for such a code comprises a buffer memory to hold the received data, a functional "copy" of the encoder, and associated equipment to measure the merit of the output of the encoder relative to the received data, that is, the accuracy of the decoding process. This can be performed as described in Massey, J.L., "Variable-Length Codes and the Fano Metric", IEEE Trans. Inf. Theory, IT-18, pp. 196-198, Jan. 1972, specifically according to eq. (5) on p. 198. The resulting "metric of merit" is used sequentially to estimate errors and correct the data sequence. The "branch metric" is computed branch by branch of the coding tree; the running sum of all branch metrics is called the "path metric", which is compared to a threshold. Whenever a threshold violation is found, the received data is searched backward for the probable cause and then corrected.
This estimation and backward searching can be controlled according to the well-known Fano algorithm. See Error-Correction Coding for Digital Communications, Clark and Cain, Plenum Press, 1981 (pp. 297-326). According to the Fano algorithm, and as suggested above, information bits and parity bits are transmitted, are to some degree corrupted in the channel by noise, and then are detected by the receiver. The receiver regenerates parity bits from the corrupted information bits and compares the regenerated parity bits with the received parity bits, generating the so-called "syndrome" bits. The branch metric, that is, a measure of the probability of the received sequence, is computed for each branch according to the formulas in Massey, supra. The branch metric is greater for higher probability received vectors, i.e., ones with fewer errors. A running sum of these branch metrics is compared with an adaptive threshold. Where the running sum drops below the current threshold, the detection process ceases to go forward and is reversed to re-examine the values for assumed previous information bits, until a sequence of information bits which results in an increasingly positive running sum value is obtained. The adaptive threshold is adjusted following the rules of the modified Fano algorithm.
Conventional sequential decoders can thus provide effective correction for communication errors. However, due to channel noise and other transmission path conditions, errors often cause a conventional sequential decoder to do an enormous amount of searching, which can result in the decoder simply running out of time to decode all the received information. Resynchronization of the decoder is then required. During this process, the decoder is unable to correct a quantity of data, which is lost.
Block coding is also employed in data communication arrangements. In such systems, a group of K information bits is algebraically manipulated according to a particular coding scheme (e.g. a Hamming code) to yield a number of additional bits which together with the original bits or some permutation of them make up an N-bit block. N is thus always greater than K, and the code is referred to as an K/N code. The additional bits provide redundant information which can be used to decode a limited number of errors in the received blocks. See the Clark and Cain reference mentioned above (Ch. 1-5) for a full discussion of block coding.
Block coding is distinguished from convolutional coding as discussed above in that convolutional codes use a sliding window of memory (i.e., data is encoded according to the preceding data) while the block encoder memory window advances one block at a time (i.e., data blocks are treated individually).
As far as known by the present inventors the properties and structures of both convolutional and block codes have not previously been integrated into a single code and employed on data streams.